module nazo.sort;
/**
 * ソート
 * License: Public Domain
 */
import std.stdio;

///aとbをスワップします。
void swap(T)(inout T a,inout T b) {
  T tmp=a;
  a=b;
  b=tmp;
}

/+
///arrの各要素を関数fにかけてその返り値を比較しバブルソートをします。
T[] sort(T,U)(T[] arr,U delegate(T) f){
  if(arr.length<2)
    return arr;
  for(size_t i=0;i<arr.length-1;i++){
    U t=f(arr[i]);
    for(size_t j=i+1;j<arr.length;j++){
      U u=f(arr[j]);
      if(t>u){
        swap(arr[i],arr[j]);
        t=u;
      }
    }
  }
  return arr;
}
+/
///arrの各要素を関数fにかけてその返り値を比較しコムソートをします。
T[] sort(T,U)(T[] arr,U delegate(T) f){
  if(arr.length<2)return arr;
  int gap=arr.length;
  bool sw=true;
  while(sw || gap > 1) {
    gap=(gap*10)/13;
    if(gap < 1)
      gap=1;
//    if(gap==9||gap==10)
//      gap=11;
    sw=false;
    for(int i=0; i<arr.length-gap; i++) {
      if(f(arr[i]) > f(arr[i+gap])) {
        swap(arr[i], arr[i+gap]);
        sw = true;
      }
    }
  }
  return arr;
}

unittest{
  assert(sort(cast(int[])[], delegate int(int val){return val;}) == cast(int[])[]);
  assert(sort([3], delegate int(int val){return val;}) == [3]);
  assert(sort([3,5,2,4,1], delegate int(int val){return val;}) == [1,2,3,4,5]);
}

/+
///arrの各要素を関数fにかけてその返り値を比較しバブルソートをします。
T[] sort2(T,U,V)(T[] arr,U delegate(T) f, V delegate(T) f2){
  for(size_t i=0;i<arr.length-1;i++){
    U t=f(arr[i]);
    V t2=f2(arr[i]);
    for(size_t j=i+1;j<arr.length;j++){
      U u=f(arr[j]);
      V u2=f2(arr[j]);
      if(t>u || (t == u && t2>u2)){
        swap(arr[i],arr[j]);
        t=u;
        t2=u2;
      }
    }
  }
  return arr;
}+/

///arrの各要素を関数fにかけてその返り値を比較しコムソートをします。
T[] sort2(T,U,V)(T[] arr,U delegate(T) f, V delegate(T) f2){
  if(arr.length<2)return arr;
  int gap=arr.length;
  bool sw=true;
  while(sw || gap > 1) {
    gap=(gap*10)/13;
    if(gap < 1)
      gap=1;
//    if(gap==9||gap==10)
//      gap=11;
    sw=false;
    for(int i=0; i<arr.length-gap; i++) {
      auto a=f(arr[i]),b=f(arr[i+gap]);
      if(a > b || (a == b && f2(arr[i]) > f2(arr[i+gap]))) {
        swap(arr[i], arr[i+gap]);
        sw = true;
      }
    }
  }
  return arr;
}

unittest{
  //FIXME: more better unittest needed
  assert(sort2(cast(int[])[], delegate int(int val){return 0;}, delegate int(int val){return val;}) == cast(int[])[]);
  assert(sort2([3], delegate int(int val){return 0;}, delegate int(int val){return val;}) == [3]);
  assert(sort2([3,5,2,4,1], delegate int(int val){return 0;}, delegate int(int val){return val;}) == [1,2,3,4,5]);
}
